The present invention relates to a programmable logic array circuit (hereinafter referred to as PLA) used for digital systems.
A conventional standard PLA consists, as shown in FIG. 1, of an input decode circuit 11, an AND array 12, an OR array 13, input lines 14, decoded input lines 15, product term lines 16, and output lines 17.
When the PLA is to be constituted on a chip, the required area S is approximately given by the following equation, EQU S=k.times.(n.times.2+m).times.P (1)
where n denotes the number of input lines, m denotes the number of output lines, P denotes the number of product term lines, and k denotes a constant.
In designing the PLA, it is essential to constitute the same function using a minimal area.
The PLA usually corresponds directly to an expression of a multiple-output logic function in the sum-of-products form. The PLA of FIG. 1 realizes a four-input three-output logic function which is represented by Boolean expression in FIG. 2, and wherein the input, output and product term of the logic function correspond to the input line, output line, and product term line of PLA.
In order to reduce the area S, the number P of product term lines must be decreased under a condition where the constant k, the number n of input lines, and the number m of output lines are kept unchanged in the equation (1). This, however, means that the number of product terms constituting a corresponding number of logic functions must be decreased.
Conventional arts for decreasing the number of product term lines in the PLA includes a system of partitioning inputs, for example, a method which employs a two-input four-output decoder for partitioning inputs as given in H. Fleisher and L. I. Meissel, "An introduction to array logic", IBM J. Res. Develop., Vol. 19, pp. 98-109, March 1975, and a system which is based upon the choice of correct output phase, for example, a method which selectively inserts a NOT gate into the rear stage of the OR array.
By these methods, however, there are some cases where it is not allowed to reduce the number of product term lines. Since conventional PLA's are constituted only by AND operations and OR operations, and do not have a sharp operation (an operation to a first product term to obtain a product term which is obtained by eliminating from the first product term a common part of the first product term and a second product term), such PLA's could not apply the characteristics of the sharp operation which can reduce the number of product terms of a logic function.
FIG. 3 expresses the logic functions of FIG. 2 in the form of Karnaugh maps, wherein reference numeral 31 represents that a minterm (smallest unit of product terms of a given combinational logic space) at that position is an implicant (product term contained in a given logic function) of the logic function. A loop 32 represents a product term.
As will be understood from the Karnaugh maps of FIG. 3, it is not possible to reduce any more the number of product terms constituting the logic functions with the PLA of the conventional art.